home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / gxclmem.c < prev    next >
C/C++ Source or Header  |  1997-06-11  |  32KB  |  920 lines
  1. /* Copyright (C) 1995, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.  
  3.   This file is part of Aladdin Ghostscript.
  4.  
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.  
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxclmem.c */
  20. /* RAM-based command list implementation */
  21. #include "memory_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxclmem.h"
  25.  
  26. /*
  27.  * Based on: memfile.c    Version: 1.4 3/21/95 14:59:33 by Ray Johnston.
  28.  * Copyright assigned to Aladdin Enterprises.
  29.  */
  30.  
  31. /*****************************************************************************
  32.  
  33.    This package is more or less optimal for use by the clist routines, with
  34.    a couple of the more likely to change "tuning" parameters given in the
  35.    two macros below -- NEED_TO_COMPRESS and GET_NUM_RAW_BUFFERS. Usually
  36.    the NEED_TO_COMPRESS decision will be deferred as long as possible based
  37.    on some total system free RAM space remaining.
  38.  
  39.    The data structures are in "memfile.h", and the primary 'tuning' parameter
  40.    is MEMFILE_DATA_SIZE. This should not be too small to keep the overhead
  41.    ratio of the block structures to the clist data small. A value of 16384
  42.    is probably in the ballpark.
  43.  
  44.    The concept is that a memory based "file" is created initially without
  45.    compression, with index blocks every MEMFILE_DATA_SIZE of the file. The
  46.    primary blocks (used by the memfile_fseek logic) for indexing into the
  47.    file are called 'logical' (LOG_MEMFILE_BLK) and the data in stored in a
  48.    different block called a 'physical' block (PHYS_MEMFILE_BLK). When the
  49.    file is not yet compressed, indicated by (f->phys_curr==NULL), then there
  50.    is one physical block for each logical block. The physical block also has
  51.    the 'data_limit' set to NULL if the data is not compressed. Thus when a
  52.    file is not compressed there is one physical block for each logical block.
  53.  
  54. COMPRESSION.
  55.  
  56.    When compression is triggered for a file then all of the blocks except
  57.    the last are compressed.  Compression will result in a physical block
  58.    that holds data for more than one logical block. Each logical block now
  59.    points to the start of compressed data in a physical block with the
  60.    'phys_pdata' pointer. The 'data_limit' pointer in the physical block is
  61.    where the compression logic stopped storing data (as stream data
  62.    compressors are allowed to do). The data for the logical block may span
  63.    to the next physical block. Once physical blocks are compressed, they are
  64.    chained together using the 'link' field.
  65.  
  66.    The 'f->phys_curr' points to the block being filled by compression, with
  67.    the 'f->wt.ptr' pointing to the last byte filled in the block. These are
  68.    used during subsequent compression when the last logical block of the
  69.    file fills the physical block.
  70.  
  71. DECOMPRESSION.
  72.  
  73.    During reading the clist, if the logical block points to an uncompressed
  74.    physical block, then 'memfile_get_pdata' simply sets the 'pdata' and the
  75.    'pdata_end' pointers. If the logical block was compressed, then it may
  76.    still be resident in a cache of decompression buffers. The number of these
  77.    decompression buffers is not critical -- even one is enough, but having
  78.    more may prevent decompressing blocks more than once (a cache_miss). The
  79.    number of decompression buffers, called "raw" buffers, that are attempted
  80.    to allocate can be changed with the GET_NUM_RAW_BUFFERS macro, but no
  81.    error occurs if less than that number can be allocated.
  82.  
  83.    If the logical block still resides in a decompression cache buffer, then
  84.    the 'raw_block' will identify the block. If the data for a logical block
  85.    only exists in compressed form, then the "tail" of the list of decompression
  86.    buffers is re-used, marking the 'raw_block' of the logical block that was
  87.    previously associated with this data to NULL.
  88.  
  89.    Whichever raw decompression buffer is accessed is moved to the head of the
  90.    decompression buffer list in order to keep the tail of the list as the
  91.    "least recently used".
  92.  
  93.    There are some DEBUG global static variables used to count the number of
  94.    cache hits "tot_cache_hits" and the number of times a logical block is
  95.    decompressed "tot_cache_miss". Note that the actual number of cache miss
  96.    events is 'f->log_length/MEMFILE_DATA_SIZE - tot_cache_miss' since we
  97.    assume that every logical block must be decmpressed at least once.
  98.  
  99.    Empirical results so far indicate that if one cache raw buffer for every
  100.    32 logical blocks, then the hit/miss ratio exceeds 99%. Of course, the
  101.    number of raw buffers should be more than 1 if possible, and in many
  102.    implementations (single threaded), the memory usage does not increase
  103.    during the page output step so almost all of memory can be used for
  104.    these raw buffers to prevent the likelihood of a cache miss.
  105.  
  106.    Of course, this is dependent on reasonably efficient clist blocking
  107.    during writing which is dependent on the data and on the BufferSpace
  108.    value which determines the number of clist band data buffers available.
  109.    Empirical testing shows that the overall efficiency is best if the
  110.    BufferSpace value is 1,000,000 (as in the original Ghostscript source).
  111.    [Note: I expected to be able to use smaller buffer sizes for some cases,
  112.     but this resulted in a high level of thrashing...RJJ]
  113.  
  114. LIMITATIONS.
  115.  
  116.    The most serious limitation is caused by the way 'memfile_fwrite' decides
  117.    to free up and re-initialize a file. If memfile_fwrite is called after
  118.    a seek to any location except the start of the file, then an error is
  119.    issued since logic is not present to properly free up on a partial file.
  120.    This is not a problem as used by the 'clist' logic since rewind is used
  121.    to position to the start of a file when re-using it after an 'erasepage'.
  122.  
  123.    Since the 'clist' logic always traverses the clist using fseek's to ever
  124.    increasing locations, no optimizations of backward seeks was implemented.
  125.    This would be relatively easy with back chain links or bi-directional
  126.    "X-OR" pointer information to link the logical block chain. The rewind
  127.    function is optimal and moves directly to the start of the file.
  128.  
  129. ********************************************************************************/
  130.  
  131. /*
  132.    The need to compress should be conditional on the amount of available
  133.    memory, but we don't have a way to communicate this to these routines.
  134.    Instead, we simply start compressing when we've allocated more than
  135.    COMPRESSION_THRESHOLD amount of data.  The threshold should be at
  136.    least as large as the fixed overhead of the compressor plus the
  137.    decompressor, plus the expected compressed size of a block that size.
  138. */
  139. private const long COMPRESSION_THRESHOLD = 300000;
  140. #define NEED_TO_COMPRESS(f)\
  141.   ((f)->ok_to_compress && (f)->total_space > COMPRESSION_THRESHOLD)
  142.  
  143.    /* FOR NOW ALLOCATE 1 raw buffer for every 32 blocks (at least 8)    */
  144. #define GET_NUM_RAW_BUFFERS( f )                     \
  145.      max(f->log_length/MEMFILE_DATA_SIZE/32, 8)
  146.  
  147. #define MALLOC(f, siz, cname)\
  148.   (void *)gs_alloc_bytes((f)->data_memory, siz, cname)
  149. #define ALLOCATE(vptr, f, cname, msg)\
  150.   vptr = MALLOC(f, sizeof(*(vptr)), cname);\
  151.   if ( !(vptr) ) {\
  152.     eprintf(msg);\
  153.     return_error(gs_error_VMerror);\
  154.   }\
  155.   (f)->total_space += sizeof(*(vptr))
  156. #define FREE(f, obj, cname)\
  157.   (gs_free_object((f)->data_memory, obj, cname),\
  158.    (f)->total_space -= sizeof(*(obj)))
  159.  
  160. /* Structure descriptor for GC */
  161. private_st_MEMFILE();
  162.  
  163.     /* forward references */
  164. private void    memfile_free_mem(P1(MEMFILE *f));
  165. private int    memfile_init_empty(P1(MEMFILE *f));
  166.  
  167. /************************************************/
  168. /*   #define DEBUG    /- force statistics -/    */
  169. /************************************************/
  170.  
  171. #ifdef DEBUG
  172. long tot_compressed;
  173. long tot_raw;
  174. long tot_cache_miss;
  175. long tot_cache_hits;
  176. long tot_swap_out;
  177. /*
  178.    The following pointers are here only for helping with a dumb debugger
  179.    that can't inspect local variables!
  180. */
  181. byte        *decomp_wt_ptr0, *decomp_wt_limit0;
  182. const byte     *decomp_rd_ptr0, *decomp_rd_limit0;
  183. byte        *decomp_wt_ptr1, *decomp_wt_limit1;
  184. const byte     *decomp_rd_ptr1, *decomp_rd_limit1;
  185. #endif
  186.  
  187. /* ---------------- Open/close/unlink ---------------- */
  188.  
  189. int
  190. memfile_fopen(char *fname, const char *fmode,
  191.   clist_file_ptr /*MEMFILE **/ *pf, gs_memory_t *mem, bool ok_to_compress)
  192. {
  193.    MEMFILE    *f;
  194.    int        code;
  195.  
  196.    /* We don't implement reopening an existing file. */
  197.    if ( fname[0] != 0 || fmode[0] != 'w' )
  198.      return_error(gs_error_invalidfileaccess);
  199.  
  200.     /* There is no need to set fname in this implementation, */
  201.     /* but we do it anyway. */
  202.    fname[0] = (ok_to_compress ? 'a' : 'b');
  203.    fname[1] = 0;
  204.  
  205.    f = gs_alloc_struct(mem, MEMFILE, &st_MEMFILE,
  206.                "memfile_open_scratch(MEMFILE)");
  207.    if ( f == NULL ) {
  208.       eprintf1("memfile_open_scratch(%s): gs_alloc_struct failed\n", fname);
  209.       return_error(gs_error_VMerror);
  210.    }
  211.    f->memory = mem;
  212. #ifdef USE_C_HEAP_FOR_DATA
  213.    f->data_memory = &gs_memory_default;
  214. #else
  215.    f->data_memory = mem;
  216. #endif
  217.    /*
  218.     * Disregard the ok_to_compress flag, since the size threshold gives us
  219.     * a much better criterion for deciding when compression is appropriate.
  220.     */
  221.    f->ok_to_compress = /*ok_to_compress*/ true;
  222.    f->compress_state = 0;    /* make clean for GC */
  223.    f->decompress_state = 0;
  224.    if ( f->ok_to_compress ) {
  225.      const stream_state *compress_proto = clist_compressor_state(NULL);
  226.      const stream_state *decompress_proto = clist_decompressor_state(NULL);
  227.      const stream_template *compress_template = compress_proto->template;
  228.      const stream_template *decompress_template = decompress_proto->template;
  229.      f->compress_state =
  230.        gs_alloc_struct(mem, stream_state, compress_template->stype,
  231.                "memfile_open_scratch(compress_state)");
  232.      f->decompress_state =
  233.        gs_alloc_struct(mem, stream_state, decompress_template->stype,
  234.                "memfile_open_scratch(decompress_state)");
  235.      if ( f->compress_state == 0 || f->decompress_state == 0 ) {
  236.        eprintf1("memfile_open_scratch(%s): gs_alloc_struct failed\n", fname);
  237.        return_error(gs_error_VMerror);
  238.      }
  239.      memcpy(f->compress_state, compress_proto,
  240.         gs_struct_type_size(compress_template->stype));
  241.      f->compress_state->memory = mem;
  242.      memcpy(f->decompress_state, decompress_proto,
  243.         gs_struct_type_size(decompress_template->stype));
  244.      f->decompress_state->memory = mem;
  245.      if ( compress_template->set_defaults )
  246.        (*compress_template->set_defaults)(f->compress_state);
  247.      if ( decompress_template->set_defaults )
  248.        (*decompress_template->set_defaults)(f->decompress_state);
  249.    }
  250.    f->total_space = 0;
  251.     /* init an empty file        */
  252.    if( (code = memfile_init_empty(f)) != 0 )
  253.       return_error(code);
  254.  
  255. #ifdef DEBUG
  256.    /* If this is the start, init some statistics.    */
  257.    /* Hack: we know the 'a' file is opened first. */
  258.    if( *fname == 'a' ) {
  259.        tot_compressed = 0;
  260.        tot_raw = 0;
  261.        tot_cache_miss = 0;
  262.        tot_cache_hits = 0;
  263.        tot_swap_out = 0;
  264.    }
  265. #endif
  266.  
  267.    *pf = f;
  268.    return 0;
  269. }
  270.  
  271. int
  272. memfile_fclose(clist_file_ptr cf, const char *fname, bool delete)
  273. {
  274.    MEMFILE *f = (MEMFILE *)cf;
  275.  
  276.    /* We don't implement closing without deletion. */
  277.    if ( !delete )
  278.      return_error(gs_error_invalidfileaccess);
  279.    memfile_free_mem(f);
  280.    gs_free_object(f->memory, f->decompress_state,
  281.           "memfile_close_and_unlink(decompress_state)");
  282.    gs_free_object(f->memory, f->compress_state,
  283.           "memfile_close_and_unlink(compress_state)");
  284.    gs_free_object(f->memory, f, "memfile_close_and_unlink(MEMFILE)");
  285.    return 0;
  286. }
  287.  
  288. int
  289. memfile_unlink(const char *fname)
  290. {
  291.   /*
  292.    * Since we have no way to represent a memfile other than by the
  293.    * pointer, we don't (can't) implement unlinking.
  294.    */
  295.   return_error(gs_error_invalidfileaccess);
  296. }
  297.  
  298. /* ---------------- Writing ---------------- */
  299.  
  300. private int
  301. compress_log_blk( MEMFILE *f, LOG_MEMFILE_BLK *bp )
  302. {
  303.    int            status;
  304.    long            compressed_size;
  305.    byte            *start_ptr;
  306.    PHYS_MEMFILE_BLK    *newphys;
  307.  
  308.    /* compress this block */
  309.    f->rd.ptr = (const byte *)(bp->phys_blk->data) - 1;
  310.    f->rd.limit = f->rd.ptr + MEMFILE_DATA_SIZE;
  311.  
  312.    bp->phys_blk = f->phys_curr;
  313.    bp->phys_pdata = (char *)(f->wt.ptr) + 1;
  314.    if ( f->compress_state->template->reinit != 0 )
  315.      (*f->compress_state->template->reinit)(f->compress_state);
  316.    compressed_size = 0;
  317.  
  318.    start_ptr = f->wt.ptr;
  319.    status = (*f->compress_state->template->process)(f->compress_state,
  320.             &(f->rd), &(f->wt), true );
  321.    bp->phys_blk->data_limit = (char *)(f->wt.ptr);
  322.  
  323.    if( status == 1 ) {    /* More output space needed (see strimpl.h)    */
  324.       /* allocate another physical block, then compress remainder    */
  325.       compressed_size = f->wt.limit - start_ptr;
  326.       ALLOCATE(newphys, f, "memfile newphys",
  327.            "compress_log_blk : MALLOC for 'newphys' failed\n");
  328.       newphys->link = NULL;
  329.       bp->phys_blk->link = newphys;
  330.       f->phys_curr = newphys;
  331.       f->wt.ptr = (byte *)(newphys->data) - 1;
  332.       f->wt.limit = f->wt.ptr + MEMFILE_DATA_SIZE;
  333.  
  334.       start_ptr = f->wt.ptr;
  335.       status = (*f->compress_state->template->process)(f->compress_state,
  336.                &(f->rd), &(f->wt), true );
  337.       if( status != 0 ) {
  338.      eprintf("Compression required more than one full block!\n");
  339.      return_error(gs_error_Fatal);
  340.       }
  341.       newphys->data_limit = (char *)(f->wt.ptr);
  342.    }
  343.  
  344.    compressed_size += f->wt.ptr - start_ptr;
  345.    if( compressed_size > MEMFILE_DATA_SIZE ) {
  346.       eprintf2("\nCompression didn't - raw=%d, compressed=%ld\n",
  347.            MEMFILE_DATA_SIZE, compressed_size);
  348.    }
  349. #ifdef DEBUG
  350.    tot_compressed += compressed_size;
  351. #endif
  352.    return(0);
  353. }    /* end "compress_log_blk()"                    */
  354.  
  355. /*    Internal (private) routine to handle end of logical block    */
  356. private int
  357. memfile_next_blk( MEMFILE *f )
  358. {
  359.    LOG_MEMFILE_BLK *bp = f->log_curr_blk;
  360.    LOG_MEMFILE_BLK *newbp;
  361.    PHYS_MEMFILE_BLK *newphys, *oldphys;
  362.  
  363.    if( f->phys_curr == NULL ) {    /* means NOT compressing         */
  364.       /* allocate a new block                        */
  365.       ALLOCATE(newphys, f, "memfile newphys",
  366.            "memfile_next_blk: MALLOC 1 for 'newphys' failed\n");
  367.       newphys->link = NULL;
  368.       newphys->data_limit = NULL;    /* raw                */
  369.  
  370.       ALLOCATE(newbp, f, "memfile newbp",
  371.            "memfile_next_blk: MALLOC 1 for 'newbp' failed\n");
  372.       bp->link = newbp;
  373.       newbp->link = NULL;
  374.       newbp->raw_block = NULL;
  375.       f->log_curr_blk = newbp;
  376.  
  377.       /* check if need to start compressing                 */
  378.       if ( NEED_TO_COMPRESS(f) ) {
  379.  
  380. #ifdef DEBUG
  381.          eprintf("Beginning compression\n");
  382. #endif
  383.          /* compress the entire file up to this point             */
  384.      if ( !f->compressor_initialized ) {
  385.         int code = 0;
  386.         if ( f->compress_state->template->init != 0 )
  387.            code = (*f->compress_state->template->init)(f->compress_state);
  388.         if ( code < 0 )
  389.            return_error(gs_error_VMerror);    /****** BOGUS ******/
  390.         if ( f->decompress_state->template->init != 0 )
  391.           code = (*f->decompress_state->template->init)
  392.             (f->decompress_state);
  393.         if ( code < 0 )
  394.            return_error(gs_error_VMerror);    /****** BOGUS ******/
  395.         f->compressor_initialized = true;
  396.      }
  397.  
  398.      /* Write into the new physical block we just allocated,    */
  399.      /* replace it after the loop (after some blocks are freed)    */
  400.      f->phys_curr = newphys;
  401.      f->wt.ptr = (byte *)(newphys->data) - 1;
  402.      f->wt.limit = f->wt.ptr + MEMFILE_DATA_SIZE;
  403.      bp = f->log_head;
  404.      while( bp != newbp ) {        /* don't compress last block     */
  405.         int code;
  406.         oldphys = bp->phys_blk;
  407.         if( (code = compress_log_blk(f,bp)) != 0 )
  408.            return_error( code );
  409.         FREE(f, oldphys, "memfile_next_blk(oldphys)");
  410.         bp = bp->link;
  411.      }    /* end while( ) compress loop                 */
  412.      /* Allocate a physical block for this (last) logical block     */
  413.      ALLOCATE(newphys, f, "memfile newphys",
  414.           "memfile_next_blk: MALLOC 2 for 'newphys' failed\n");
  415.      newphys->link = NULL;
  416.      newphys->data_limit = NULL;        /* raw            */
  417.  
  418.       }    /* end convert file to compressed                 */
  419.  
  420.       newbp->phys_blk = newphys;
  421.       f->pdata = newphys->data;
  422.       f->pdata_end = newphys->data + MEMFILE_DATA_SIZE;
  423.    }    /* end if NOT compressing                    */
  424.  
  425.     /* File IS being compressed                     */
  426.    else {
  427.       int code;
  428.       oldphys = bp->phys_blk;    /* save raw phys block ID        */
  429.       /* compresses bp on phys list    */
  430.       if( (code = compress_log_blk(f,bp)) != 0 )
  431.      return_error( code );
  432.       ALLOCATE(newbp, f, "memfile newbp",
  433.            "memfile_next_blk: MALLOC 2 for 'newbp' failed\n");
  434.       bp->link = newbp;
  435.       newbp->link = NULL;
  436.       newbp->raw_block = NULL;
  437.       /* Re-use the raw phys block for this new logical blk         */
  438.       newbp->phys_blk = oldphys;
  439.       f->pdata = oldphys->data;
  440.       f->pdata_end = f->pdata + MEMFILE_DATA_SIZE;
  441.       f->log_curr_blk = newbp;
  442.    }     /* end else (when we are compressing)                */
  443.  
  444.    return( 0 );
  445. }
  446.  
  447. int
  448. memfile_fwrite_chars(const void *data, uint len, clist_file_ptr cf)
  449. {
  450.    const char *str = (const char *)data;
  451.    MEMFILE *f = (MEMFILE *)cf;
  452.    uint count = len;
  453.    int status;
  454.  
  455.    /* check if we are writing to the start of the file.  If so, then    */
  456.    /* free the file memory and re-initialize it (frees memory)        */
  457.    if( f->log_curr_pos == 0 ) {
  458.       memfile_free_mem( f );
  459.       memfile_init_empty( f );
  460.    }
  461.  
  462.    if( f->log_curr_blk->link != 0 ) {
  463.       eprintf(" Write file truncate -- need to free physical blocks.\n");
  464.    }
  465.  
  466.    while( count ) {
  467.      uint move_count = f->pdata_end - f->pdata;
  468.      if ( move_count == 0 ) {
  469.      if( (status = memfile_next_blk( f )) != 0 ) {
  470.         f->error_code = status;
  471.         return( 0 );
  472.      }
  473.      } else {
  474.        if ( move_count > count )
  475.      move_count = count;
  476.        memmove(f->pdata, str, move_count);
  477.        f->pdata += move_count;
  478.        str += move_count;
  479.        count -= move_count;
  480.      }
  481.    }
  482.    f->log_curr_pos += len;
  483.    f->log_length = f->log_curr_pos;    /* truncate length to here    */
  484. #ifdef DEBUG
  485.    tot_raw += len;
  486. #endif
  487.    return(len);
  488. }
  489.  
  490. /*                                    */
  491. /*    Internal routine to set the f->pdata and f->pdata_end pointers    */
  492. /*    for the current logical block f->log_curr_blk            */
  493. /*                                    */
  494. /*    If data only exists in compressed form, allocate a raw buffer    */
  495. /*    and decompress it.                        */
  496. /*                                    */
  497.  
  498. private int
  499. memfile_get_pdata( MEMFILE *f )
  500. {
  501.    int            i, num_raw_buffers, status;
  502.    LOG_MEMFILE_BLK    *bp = f->log_curr_blk;
  503.  
  504.    if( bp->phys_blk->data_limit == NULL ) {
  505.       /* Not compressed, return this data pointer             */
  506.       f->pdata =  (bp->phys_blk)->data;
  507.       i = f->log_curr_pos % MEMFILE_DATA_SIZE;    /* pos within block    */
  508.       i = f->log_curr_pos - i;            /* base of block    */
  509.       if( i+MEMFILE_DATA_SIZE > f->log_length )
  510.      f->pdata_end = f->pdata + f->log_length - i;
  511.       else
  512.      f->pdata_end =  f->pdata + MEMFILE_DATA_SIZE;
  513.    }
  514.    else {
  515.       /* data was compressed                        */
  516.       if( f->raw_head == NULL ) {
  517.      /* need to allocate the raw buffer pool            */
  518.      num_raw_buffers = GET_NUM_RAW_BUFFERS( f );
  519.      ALLOCATE(f->raw_head, f, "memfile raw buffer",
  520.           "memfile_get_pdata: MALLOC for 'raw_head' failed\n");
  521.      f->raw_head->back = NULL;
  522.      f->raw_tail = f->raw_head;
  523.      f->raw_tail->log_blk = NULL;
  524.      for( i=0; i<num_raw_buffers; i++ ) {
  525.         f->raw_tail->fwd = (RAW_BUFFER *) MALLOC(f, sizeof(RAW_BUFFER),
  526.                              "memfile raw buffer");
  527.            /* if MALLOC fails, then just stop allocating         */
  528.         if( ! f->raw_tail->fwd ) break;
  529.         f->total_space += sizeof(RAW_BUFFER);
  530.         f->raw_tail->fwd->back = f->raw_tail;
  531.         f->raw_tail = f->raw_tail->fwd;
  532.         f->raw_tail->log_blk = NULL;
  533.      }
  534.      f->raw_tail->fwd = NULL;
  535.      num_raw_buffers = i+1;        /* if MALLOC failed, then OK    */
  536. #ifdef DEBUG
  537.      eprintf1("\nNumber of raw buffers allocated=%d\n", num_raw_buffers );
  538. #endif
  539.       } /* end allocating the raw buffer pool (first time only)        */
  540.  
  541.       if( bp->raw_block == NULL ) {
  542. #ifdef DEBUG
  543.      tot_cache_miss++;        /* count every decompress    */
  544. #endif
  545.      /* find a raw buffer and decompress                */
  546.      if( f->raw_tail->log_blk != NULL ) {
  547.         /* This block was in use, grab it                */
  548. #ifdef DEBUG
  549.         tot_swap_out++;
  550. #endif
  551.         f->raw_tail->log_blk->raw_block = NULL; /* data no longer here */
  552.         f->raw_tail->log_blk = NULL;
  553.      }
  554.      /* Use the last raw block in the chain (the oldest)        */
  555.      f->raw_tail->back->fwd = NULL;        /* disconnect from tail    */
  556.      f->raw_tail->fwd = f->raw_head;    /* new head        */
  557.      f->raw_head->back = f->raw_tail;
  558.      f->raw_tail = f->raw_tail->back;
  559.      f->raw_head = f->raw_head->back;
  560.      f->raw_head->back = NULL;
  561.      f->raw_head->log_blk = bp;
  562.  
  563.      /* Decompress the data into this raw block            */
  564.         /* Initialize the decompressor                 */
  565.      if ( f->decompress_state->template->reinit != 0 )
  566.        (*f->decompress_state->template->reinit)(f->decompress_state);
  567.         /* Set pointers and call the decompress routine        */
  568.      f->wt.ptr = (byte *)(f->raw_head->data) - 1;
  569.      f->wt.limit = f->wt.ptr + MEMFILE_DATA_SIZE;
  570.      f->rd.ptr = (const byte *)(bp->phys_pdata) - 1;
  571.      f->rd.limit = (const byte *)bp->phys_blk->data_limit;
  572. #ifdef DEBUG
  573.      decomp_wt_ptr0 = f->wt.ptr;
  574.      decomp_wt_limit0 = f->wt.limit;
  575.      decomp_rd_ptr0 = f->rd.ptr;
  576.      decomp_rd_limit0 = f->rd.limit;
  577. #endif
  578.      status = (*f->decompress_state->template->process)
  579.        (f->decompress_state, &(f->rd), &(f->wt), true );
  580.      if( status == 0 ) {    /* More input data needed */
  581.         /* switch to next block and continue decompress         */
  582.         int back_up = 0;        /* adjust pointer backwards    */
  583.         if( f->rd.ptr != f->rd.limit ) {
  584.            /* transfer remainder bytes from the previous block    */
  585.            back_up = f->rd.limit - f->rd.ptr;
  586.            for( i=0; i<back_up; i++ )
  587.           *(bp->phys_blk->link->data - back_up + i) = *++f->rd.ptr;
  588.         }
  589.         f->rd.ptr = (const byte *)bp->phys_blk->link->data - back_up - 1;
  590.         f->rd.limit = (const byte *)bp->phys_blk->link->data_limit;
  591. #ifdef DEBUG
  592.         decomp_wt_ptr1 = f->wt.ptr;
  593.         decomp_wt_limit1 = f->wt.limit;
  594.         decomp_rd_ptr1 = f->rd.ptr;
  595.         decomp_rd_limit1 = f->rd.limit;
  596. #endif
  597.         status = (*f->decompress_state->template->process)
  598.           (f->decompress_state, &(f->rd), &(f->wt), true );
  599.         if( status == 0 ) {
  600.            eprintf("Decompression required more than one full block!\n");
  601.            return_error(gs_error_Fatal);
  602.         }
  603.      }
  604.      bp->raw_block = f->raw_head;    /* point to raw block        */
  605.       }    /* end if( raw_block == NULL ) meaning need to decompress data    */
  606.       else {
  607.      /* data exists in the raw data cache, if not raw_head, move it    */
  608.      if( bp->raw_block != f->raw_head ) {
  609.         /*         move to raw_head                */
  610.         /*         prev.fwd = this.fwd                */
  611.         bp->raw_block->back->fwd = bp->raw_block->fwd;
  612.         if( bp->raw_block->fwd != NULL )
  613.             /*         next.back = this.back            */
  614.            bp->raw_block->fwd->back = bp->raw_block->back;
  615.         else
  616.            f->raw_tail = bp->raw_block->back; /* tail = prev    */
  617.         f->raw_head->back = bp->raw_block;    /* head.back = this    */
  618.         bp->raw_block->fwd = f->raw_head;    /* this.fwd = orig head    */
  619.         f->raw_head = bp->raw_block;    /* head = this        */
  620.         f->raw_head->back = NULL;        /* this.back = NULL    */
  621. #ifdef DEBUG
  622.         tot_cache_hits++;    /* counting here prevents repeats since */
  623.                 /* won't count if already at head    */
  624. #endif
  625.      }
  626.       }
  627.       f->pdata = bp->raw_block->data;
  628.       f->pdata_end =  f->pdata + MEMFILE_DATA_SIZE;
  629.       /* NOTE: last block is never compressed, so a compressed block    */
  630.       /*    is always full size.                    */
  631.    } /* end else (when data was compressed)                 */
  632.  
  633.    return(0);
  634. }
  635.  
  636. /* ---------------- Reading ---------------- */
  637.  
  638. int
  639. memfile_fread_chars(void *data, uint len, clist_file_ptr cf)
  640. {
  641.    char *str = (char *)data;
  642.    MEMFILE *f = (MEMFILE *)cf;
  643.    uint count = len, num_read, move_count;
  644.  
  645.    num_read = f->log_length - f->log_curr_pos;
  646.    if( count > num_read )
  647.       count = num_read;
  648.    num_read = count;
  649.  
  650.    while( count ) {
  651.       f->log_curr_pos++;        /* move into next byte */
  652.       if( f->pdata == f->pdata_end ) {
  653.      f->log_curr_blk = (f->log_curr_blk)->link;
  654.          memfile_get_pdata( f );
  655.       }
  656.       move_count = f->pdata_end - f->pdata;
  657.       if ( move_count > count )
  658.     move_count = count;
  659.       f->log_curr_pos += move_count - 1;    /* new position     */
  660.       memmove(str, f->pdata, move_count);
  661.       str += move_count;
  662.       f->pdata += move_count;
  663.       count -= move_count;
  664.    }
  665.  
  666.    return( num_read );
  667. }
  668.  
  669. /* ---------------- Position/status ---------------- */
  670.  
  671. int
  672. memfile_ferror_code(clist_file_ptr cf)
  673. {
  674.    return( ((MEMFILE *)cf)->error_code );    /* errors stored here */
  675. }
  676.  
  677. long
  678. memfile_ftell(clist_file_ptr cf)
  679. {
  680.    return( ((MEMFILE *)cf)->log_curr_pos );
  681. }
  682.  
  683. void
  684. memfile_rewind(clist_file_ptr cf, bool discard_data, const char *ignore_fname)
  685. {
  686.    MEMFILE *f = (MEMFILE *)cf;
  687.  
  688.    if ( discard_data ) {
  689.      memfile_free_mem(f);
  690.      /* We have to call memfile_init_empty to preserve invariants. */
  691.      memfile_init_empty(f);
  692.    } else {
  693.      f->log_curr_blk = f->log_head;
  694.      f->log_curr_pos = 0;
  695.      memfile_get_pdata( f );
  696.    }
  697. }
  698.  
  699. int
  700. memfile_fseek(clist_file_ptr cf, long offset, int mode, const char *ignore_fname)
  701. {
  702.    MEMFILE *f = (MEMFILE *)cf;
  703.    long i, block_num, new_pos;
  704.  
  705.    switch( mode ) {
  706.       case SEEK_SET:    /* offset from the beginning of the file */
  707.      new_pos = offset;
  708.      break;
  709.  
  710.        case SEEK_CUR:    /* offset from the current position in the file */
  711.      new_pos = offset + f->log_curr_pos;
  712.      break;
  713.  
  714.       case SEEK_END:    /* offset back from the end of the file */
  715.      new_pos = f->log_length - offset;
  716.      break;
  717.  
  718.       default:
  719.      return (-1);
  720.    }
  721.    if ( new_pos < 0 || new_pos > f->log_length )
  722.      return -1;
  723.    if( (f->pdata == f->pdata_end) && (f->log_curr_blk->link != NULL) ) {
  724.       /* log_curr_blk is actually one block behind log_curr_pos        */
  725.       f->log_curr_blk = f->log_curr_blk->link;
  726.    }
  727.    block_num = new_pos / MEMFILE_DATA_SIZE;
  728.    i = f->log_curr_pos / MEMFILE_DATA_SIZE;
  729.    if ( block_num < i )        /* if moving backwards, start at beginning */
  730.      { f->log_curr_blk = f->log_head;
  731.        i = 0;
  732.      }
  733.    for ( ; i < block_num; i++ )
  734.      { f->log_curr_blk = f->log_curr_blk->link;
  735.      }
  736.    f->log_curr_pos = new_pos;
  737.    memfile_get_pdata( f );    /* pointers to start of block         */
  738.    f->pdata += new_pos - (block_num * MEMFILE_DATA_SIZE);
  739.  
  740.    return 0;        /* return "normal" status            */
  741. }
  742.  
  743. /* ---------------- Internal routines ---------------- */
  744.  
  745. private void
  746. memfile_free_mem( MEMFILE *f )
  747. {
  748.    LOG_MEMFILE_BLK *bp, *tmpbp;
  749.  
  750. #ifdef DEBUG
  751.    /* output some diagnostics about the effectiveness            */
  752.    if( tot_raw > 100 ) {
  753.       eprintf2("\n\ttot_raw=%ld, tot_compressed=%ld\n",
  754.            tot_raw, tot_compressed );
  755.    }
  756.  
  757.    if( tot_cache_hits != 0 ) {
  758.    eprintf3("\n\tCache hits=%ld, cache misses=%ld, swapouts=%ld\n",
  759.         tot_cache_hits,
  760.         tot_cache_miss - (f->log_length/MEMFILE_DATA_SIZE), tot_swap_out);
  761.    }
  762.    tot_raw = 0;
  763.    tot_compressed = 0;
  764.    tot_cache_hits = 0;
  765.    tot_cache_miss = 0;
  766.    tot_swap_out = 0;
  767. #endif
  768.  
  769.       /* Free up memory that was allocated for the memfile        */
  770.    bp = f->log_head;
  771.  
  772. /******************************************************************
  773.  * The following was the original algorithm here.  This algorithm has a bug:
  774.  * the second loop references the physical blocks again after they have been
  775.  * freed.
  776.  ******************************************************************/
  777.  
  778. #if 0        /**************** ****************/
  779.  
  780.    if ( bp != NULL ) {
  781.       /* Free the physical blocks that make up the compressed data    */
  782.      PHYS_MEMFILE_BLK *pphys = (f->log_head)->phys_blk;
  783.      if( pphys->data_limit != NULL ) {
  784.        /* the data was compressed, free the chain of blocks        */
  785.        while( pphys != NULL ) {
  786.      PHYS_MEMFILE_BLK *tmpphys = pphys->link;
  787.  
  788.      FREE(f, pphys, "memfile_free_mem(pphys)");
  789.      pphys = tmpphys;
  790.        }
  791.      }
  792.    }
  793.  
  794.       /* free the logical blocks                     */
  795.    while( bp != NULL ) {
  796.     /* if this logical block was not compressed, free the phys_blk    */
  797.       if( bp->phys_blk->data_limit == NULL ) {
  798.      FREE(f, bp->phys_blk, "memfile_free_mem(phys_blk)");
  799.       }
  800.       tmpbp = bp->link;
  801.       FREE(f, bp, "memfile_free_mem(log_blk)");
  802.       bp = tmpbp;
  803.    }
  804.  
  805. #else        /**************** ****************/
  806. # if 1        /**************** ****************/
  807.  
  808. /****************************************************************
  809.  * This algorithm is correct (we think).
  810.  ****************************************************************/
  811.  
  812.    if ( bp != NULL ) {
  813.      /* Null out phys_blk pointers to compressed data. */
  814.      PHYS_MEMFILE_BLK *pphys = bp->phys_blk;
  815.      { for ( tmpbp = bp; tmpbp != NULL; tmpbp = tmpbp->link )
  816.          if ( tmpbp->phys_blk->data_limit != NULL )
  817.        tmpbp->phys_blk = 0;
  818.      }
  819.       /* Free the physical blocks that make up the compressed data    */
  820.      if( pphys->data_limit != NULL ) {
  821.        /* the data was compressed, free the chain of blocks        */
  822.        while( pphys != NULL ) {
  823.      PHYS_MEMFILE_BLK *tmpphys = pphys->link;
  824.  
  825.      FREE(f, pphys, "memfile_free_mem(pphys)");
  826.      pphys = tmpphys;
  827.        }
  828.      }
  829.    }
  830.  
  831.    /* Now free the logical blocks, and any uncompressed physical blocks. */
  832.    while( bp != NULL ) {
  833.       if( bp->phys_blk != NULL ) {
  834.     FREE(f, bp->phys_blk, "memfile_free_mem(phys_blk)");
  835.       }
  836.       tmpbp = bp->link;
  837.       FREE(f, bp, "memfile_free_mem(log_blk)");
  838.       bp = tmpbp;
  839.    }
  840.  
  841. /***********************************************************************
  842.  * This algorithm appears to be both simpler and free of the bug that
  843.  * occasionally causes the older one to reference freed blocks; but in
  844.  * fact it can miss blocks, because the very last compressed logical block
  845.  * can have spill into a second physical block, which is not referenced by
  846.  * any logical block.
  847.  ***********************************************************************/
  848.  
  849. # else        /**************** ****************/
  850.  
  851.    { PHYS_MEMFILE_BLK *prev_phys = 0;
  852.  
  853.      while ( bp != NULL ) {
  854.        PHYS_MEMFILE_BLK *phys = bp->phys_blk;
  855.        if ( phys != prev_phys ) {
  856.      FREE(f, phys, "memfile_free_mem(phys_blk)");
  857.      prev_phys = phys;
  858.        }
  859.       tmpbp = bp->link;
  860.       FREE(f, bp, "memfile_free_mem(log_blk)");
  861.       bp = tmpbp;
  862.      }
  863.    }
  864.  
  865. # endif        /**************** ****************/
  866. #endif        /**************** ****************/
  867.  
  868.    f->log_head = NULL;
  869.  
  870.      /* Free any internal compressor state. */
  871.    if ( f->compressor_initialized ) {
  872.       if ( f->decompress_state->template->release != 0 )
  873.         (*f->decompress_state->template->release)(f->decompress_state);
  874.       if ( f->compress_state->template->release != 0 )
  875.         (*f->compress_state->template->release)(f->compress_state);
  876.       f->compressor_initialized = false;
  877.    }
  878.  
  879.       /* free the raw buffers                        */
  880.    while( f->raw_head != NULL ) {
  881.      RAW_BUFFER *tmpraw = f->raw_head->fwd;
  882.  
  883.      FREE(f, f->raw_head, "memfile_free_mem(raw)");
  884.      f->raw_head = tmpraw;
  885.    }
  886. }
  887.  
  888. private int
  889. memfile_init_empty( MEMFILE *f )
  890. {
  891.    PHYS_MEMFILE_BLK *pphys;
  892.  
  893.    /* File empty - get a physical mem block (includes the buffer area)    */
  894.    f->phys_curr = NULL;     /* flag as file not compressed        */
  895.    ALLOCATE(pphys, f, "memfile pphys",
  896.         "memfile_init_empty: MALLOC for 'pphys' failed\n");
  897.    pphys->data_limit = NULL;            /* raw data for now     */
  898.  
  899.    ALLOCATE(f->log_curr_blk, f, "memfile log blk",
  900.         "memfile_init_empty: MALLOC for log_curr_blk failed\n");
  901.    f->log_head = f->log_curr_blk;
  902.    f->log_curr_blk->link = NULL;
  903.    f->log_curr_blk->phys_blk = pphys;
  904.    f->log_curr_blk->phys_pdata = NULL;
  905.    f->log_curr_blk->raw_block = NULL;
  906.  
  907.    f->log_curr_pos = 0;
  908.    f->log_length = 0;
  909.    f->pdata = pphys->data;
  910.    f->pdata_end = f->pdata + MEMFILE_DATA_SIZE;
  911.    f->raw_head = NULL;
  912.  
  913.    f->error_code = 0;
  914.  
  915.       /* Tag the compressor state as uninitialized            */
  916.    f->compressor_initialized = false;
  917.  
  918.    return 0;
  919. }
  920.